Given a graph with n (2 ≤ n ≤ 5,000) vertices numbered 1 to n and m (1 ≤ m ≤ 30,000) undirected, weighted
edges, compute the maximum flow / minimum cut from vertex 1 to vertex n.
Input. The first line contains the two integers n and m. The next m lines each contain three
integers A, B, and C, denoting that there is an edge of capacity C (1 ≤ C
≤ 109) between nodes A and B (1 ≤ A, B ≤ n). Note that it is possible
for there to be duplicate edges, as well as an edge from a node to itself.
Output. Print a single integer (which may not fit into a 32-bit
integer) denoting the maximum flow / minimum cut between 1 and n.
Sample Input
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3
Sample Output
5
Viewing the problem as max-flow, we may send 3 units
of flow through the path 1 - 2 - 3 - 4 and 2 units of flow through the path 1 -
3 - 4. Viewing the problem as min-cut, we may cut the first and third edges.
Either way the total is 5.
ìàêñèìàëüíûé ïîòîê
Äëÿ íàõîæäåíèÿ
ìàêñèìàëüíîãî ïîòîêà çàïóñòèì àëãîðèòì Äèíèöà. Ãðàô ïðåäñòàâëåí ñïèñêîì
ñìåæíîñòè.
Ðåàëèçàöèÿ àëãîðèòìà
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX 101
#define INF 0x3F3F3F3F
using namespace
std;
class Edge
{
public:
int vTo;
long long Cap, Flow;
Edge(int vTo, long long Cap, long long Flow)
: vTo(vTo),
Cap(Cap), Flow(Flow) {}
};
class Graph
{
public:
int n;
vector<vector<int> > g;// ðåáðà
ãðàôà = ÷èñëà-óêàçàòåëè íà ðåàëüíûå ðåáðà â AllEdges
vector<Edge>
AllEdges; // Ðåàëüíûå ðåáðà ãðàôà
vector<int> ptr, d;
Graph(int n = 1) : n(n)
{
g.assign(n+1,vector<int>());
}
void AddNotOrientedEdge(int
From, int To, int
Len)
{
Edge e1 =
Edge(To,Len,0);
g[From].push_back(AllEdges.size());
AllEdges.push_back(e1);
Edge e2 =
Edge(From,Len,0);
g[To].push_back(AllEdges.size());
AllEdges.push_back(e2);
}
long long bfs(int s)
{
int qHead = 0, qTail = 0;
int *q = new int[n+1];
q[qTail++] = s;
d.assign(n+1,-1);
d[s] = 0;
while (qHead < qTail)
{
int v = q[qHead++];
for (int i = 0; i
< g[v].size(); i++)
{
Edge e =
AllEdges[g[v][i]];
int to = e.vTo;
if ((d[to] == -1) && (e.Flow < e.Cap))
{
q[qTail++] =
to;
d[to] = d[v]
+ 1;
}
}
}
delete[] q;
return d[n] != -1;
}
long long dfs(int v, long long flow)
{
if (!flow) return 0;
if (v == n) return flow;
for (int &i =
ptr[v]; flow && (i < (int)g[v].size());
i++)
{
int EdgeId = g[v][i];
Edge e =
AllEdges[EdgeId];
int to = e.vTo;
if (d[to] != d[v] + 1) continue;
long long pushed =
dfs(to, min(flow, e.Cap - e.Flow));
if (pushed)
{
AllEdges[EdgeId].Flow += pushed;
AllEdges[EdgeId
^ 1].Flow -= pushed;
return pushed;
}
}
return 0;
}
long long Dinic(int Start)
{
long long flow = 0;
for (;;)
{
if (!bfs(Start)) break;
ptr.assign(n+1,0);
while (long long pushed = dfs(Start, INF))
flow += pushed;
}
return flow;
}
};
Graph *g;
int u, v, Len, n, Edges;
int main(void)
{
scanf("%d %d",&n,&Edges);
g = new Graph(n);
while (Edges--)
{
scanf("%d %d %d",&u,&v,&Len);
if (u != v) g->AddNotOrientedEdge(u,v,Len);
}
printf("%lld\n",g->Dinic(1));
return 0;
}